COCI/2009-2010/Contest #7 - 24.04.2010/svemir/svemir.cpp

   1 #include <iostream>
   2 #include <algorithm>
   3 #include <vector>
   4 #include <cassert>
   5
   6 #define D(x) cout << #x " = " << (x) << endl
   7 using namespace std;
   8
   9 struct point {
  10   int x, y, z;
  11 };
  12
  13 int dist(point &a, point &b){
  14   int dx = abs(a.x - b.x);
  15   int dy = abs(a.y - b.y);
  16   int dz = abs(a.z - b.z);
  17   return min(dx, min(dy, dz));
  18 }
  19
  20 const int MAXNODES = 100000;
  21 int p[MAXNODES], rank[MAXNODES];
  22 void make_set(int x){ p[x] = x, rank[x] = 0; }
  23 void link(int x, int y){
  24   if (rank[x] > rank[y]) p[y] = x;
  25   else{ p[x] = y; if (rank[x] == rank[y]) rank[y]++; }
  26 }
  27 int find_set(int x){
  28   return x != p[x] ? p[x] = find_set(p[x]) : p[x];
  29 }
  30 void merge(int x, int y){ link(find_set(x), find_set(y)); }
  31
  32
  33 int main(){
  34   int n;
  35   cin >> n;
  36   vector<point> p(n);
  37   for (int i = 0; i < n; ++i){
  38     cin >> p[i].x >> p[i].y >> p[i].z;
  39     make_set(i);
  40   }
  41
  42   vector< pair<int, pair<int, int> > > edges;
  43   for (int i = 0; i < n; ++i){
  44     for (int j = i + 1; j < n; ++j){
  45       edges.push_back(make_pair( dist(p[i], p[j]), make_pair(i, j)));
  46     }
  47   }
  48   sort(edges.begin(), edges.end());
  49   int ans = 0;
  50   for (int i = 0; i < edges.size(); ++i){
  51     int u = edges[i].second.first;
  52     int v = edges[i].second.second;
  53     int w = edges[i].first;
  54     if (find_set(u) != find_set(v)){
  55       ans += w;
  56       merge(u, v);
  57     }
  58   }
  59   cout << ans << endl;
  60
  61
  62   return 0;
  63 }